package demo.structrue.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeBs2<E extends Comparable<E>> {
    public static void main(String[] args) {
        TreeBs2<Integer> bs = new TreeBs2<>();
        bs.addNode(33);
        bs.addNode(10);
        bs.addNode(40);
        bs.addNode(88);
        bs.addNode(11);
        bs.addNode(5);
        //    33
       // 10     40
    //  5   11    88

        System.out.println("======递归前序遍历========");
        bs.beforEach(bs.root);//递归前序遍历
        System.out.println("======递归后序遍历========");
        bs.endEach(bs.root);//递归后序遍历

        System.out.println("======递归中序遍历========");
        bs.middleEach(bs.root);//递归中序遍历

        System.out.println("======递归的前序遍历========");
        bs.beforEach();//递归的前序遍历

        System.out.println("======非递归的前序遍历========");
        bs.beforEachNR();   //非递归的前序遍历


        System.out.println("======层级遍历========");
        bs.levelEachNR();
    }

    private class Node implements Comparable<Node> {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }

        @Override
        public int compareTo(Node o) {
            return this.e.compareTo(o.e);
        }
    }


    private Node root = null;
    private int size = 0;

    public TreeBs2() {

    }

    public int size() {
        return size;
    }


    public boolean isEmpty() {
        return size == 0;
    }

    public void addNode(E e) {
        Node tnode = new Node(e);
        root = addNode(root, tnode);
    }

    public boolean find(E e) {
        return find(root, new Node(e));
    }

    private boolean find(Node rnode, Node tnode) {
        if (rnode==null)
            return  false;
        if (rnode.compareTo(tnode) == 0)
            return true;
        else if (rnode.compareTo(tnode) <= 0) {
            return find(rnode.right, tnode);
        } else { //rnode.compareTo(tnode) > 0
            return find(rnode.left, tnode);
        }
    }


    /**
     * 当前节点的  根节点
     * @param rnode
     * @param tnode
     * @return
     */
    private Node addNode(Node rnode, Node tnode) {
        if (rnode == null) {
            size++;
            return tnode;
        }
        if (rnode.compareTo(tnode) <= 0) {
            rnode.right = addNode(rnode.right, tnode);
        }
        if (rnode.compareTo(tnode) > 0) {
            rnode.left = addNode(rnode.left, tnode);
        }
        return rnode;
    }


    public void beforEach(){
        beforEach(root);
    }

    private void beforEach(Node node){//前序遍历
        if (node==null)
            return;

        System.out.println(node.e);
        beforEach(node.right);
        beforEach(node.left);
    }


    private void middleEach(Node node){//中序遍历，特点：输出的结果按大小顺序输出
        if (node==null)
            return;

        middleEach(node.right);
        System.out.println(node.e);
        middleEach(node.left);
    }

    private void endEach(Node node){//后序遍历
        if (node==null)
            return;

        endEach(node.right);
        endEach(node.left);
        System.out.println(node.e);
    }


    private void beforEachNR(){//前序遍历  非递归
        Stack<Node> stack= new Stack<>();
        stack.push(root);
        while ( !stack.empty()){
            Node node = stack.pop();
            System.out.println(node.e);
            if(node.left!=null)
                stack.push(node.left);
            if(node.right!=null)
                stack.push(node.right);
        }
    }



    private void levelEachNR(){//层级遍历  非递归
        Queue<Node> queue= new LinkedList<>();

        queue.add(root);
        while ( !queue.isEmpty()){
            Node node = queue.remove();
            System.out.println(node.e);
            if(node.left!=null)
                queue.add(node.left);
            if(node.right!=null)
                queue.add(node.right);
        }
    }

}
